#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 143. 重排链表.py
@time: 2022/1/13 14:08
@desc: https://leetcode-cn.com/problems/reorder-list/
> 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
    - L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
    L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

@解题思路：
    1. 先找到中点
    2. 反转后半部分（记得断链）
    3. 合并前后两部分
    4. Ot(N), Os(1)
'''
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        def findmid(head):
            quick, slow = head, head
            while quick.next and quick.next.next:
                quick = quick.next.next
                slow = slow.next
            return slow

        def reverse(head):
            p, pre = head, None
            while p:
                next = p.next
                p.next = pre
                pre = p
                p = next
            return pre

        def merge(l1, l2):
            while l1 and l2:
                l1_next = l1.next
                l2_next = l2.next
                l1.next = l2
                l1 = l1_next
                l2.next = l1
                l2 = l2_next

        # 找到中点
        mid = findmid(head)

        l1 = head
        l2 = mid.next
        # 前半部分断链
        mid.next = None
        # 反转后半部分
        l2 = reverse(l2)
        # 合并列表
        merge(l1, l2)
        return l1


if __name__ == '__main__':
    head = ListNode(1, next=ListNode(2, next=ListNode(3, next=ListNode(4, next=ListNode(5)))))
    head = Solution().reorderList(head)
    while head:
        print(head.val, end=', ')
        head = head.next